package com.sx.sx1.lintcode.day717;
import java.util.*;


public class LC135 {

    static class Solution {
        /**
         * @param candidates: A list of integers
         * @param target:     An integer
         * @return: A list of lists of integers
         * we will sort your return value in output
         */
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> ans = new ArrayList<>();
            Set<String>  visited = new HashSet<>();
            List<Integer> path = new ArrayList<>();
            Arrays.sort(candidates);
            dfs(candidates,0,0,target,path,visited,ans);
            return ans;
        }

        public void dfs(int[] arr,int idx,int sum,int target,List<Integer> path,Set<String> visited,List<List<Integer>> ans){
            if(sum> target) return;
            if(sum == target){
                if(visited.contains(path.toString()))
                    return;
                ans.add(new ArrayList<>(path));
                visited.add(path.toString());
            }else{
                for (int i = idx; i <arr.length; i++) {
                    path.add(arr[i]);
                    dfs(arr,i,sum+arr[i],target,path,visited,ans);
                    path.remove(path.size()-1);  //恢复现场
                }
            }
        }

    }

    public static void main(String[] args) {
        int[] arr1 = {2,3,6,7};
        System.out.println(new Solution().combinationSum(arr1,7));
        System.out.println(new Solution().combinationSum(new int[]{1},3));
    }
}




/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
135 · 数字组合
算法
中等
通过率
39%

题目
题解75
笔记
讨论99+
排名
记录
描述
给定一个候选数字的集合 candidates 和一个目标值 target。 找到 candidates 中所有的和为 target 的组合。

在同一个组合中, candidates 中的某个数字出现次数不限。

所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.
解集不能包含重复的组合.
样例
样例 1:

输入: candidates = [2, 3, 6, 7], target = 7
输出: [[7], [2, 2, 3]]
样例 2:

输入: candidates = [1], target = 3
输出: [[1, 1, 1]]
相关知识
学习《2024年7月北美大厂最新面试真题精讲》课程中的3.5Meta：最新面试精选003相关内容 ，了解更多相关知识！
标签
相关题目

153
数字组合 II
中等

739
24点
困难

740
零钱兑换 2
中等

653
添加运算符
困难

652
因式分解
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
134/3325
已开启智能提示
发起考试
30 分 00 秒
1234567891011

    控制台
            历史提交

 */
